package 链表.LRU缓存;

import java.util.HashMap;
import java.util.Map;
/**
 * 题目描述：
 * 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。
 * 缓存应该最近最少使用的顺序来维护。
 * 缓存应该支持以下操作： 获取数据 get 和 写入数据 put 。
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。
 * 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 * 缓存容量 capacity - 缓存的最大容量。
 * 示例:
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 * 输入
 * ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
 * [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
 * 输出
 * [null, null, null, 1, null, -1, null, -1, 3, 4]
 * 最近最少访问的结点
 * 力扣地址：https://leetcode-cn.com/problems/lru-cache/
 * 力扣第 146 题
 * */
/**
 * 题目理解 ：
 * 首先看题有存储就可以想到哈希表
 * 顺序存储可以想到链表
 * 可以想象是一堆书
 * get 从书堆中拿出一本书放到最上面
 * put 放入一本新书，如果这本书存在，就把它放在最上面替换他的value
 * 例如将第二版的书替换为第三本书
 * 如果没有这本书（key），就放在最上面
 * 如果超过这本书，就把下面的书移除
 * */
/**
 * 题目思路：
 * get，拿出来放到链表的头部，判断是否为空。如果为空，返回-1，不为空返回value的值
 * put，检查节点是否存在，如果存在，改变一下他的value就可以了
 * 没有节点的话就创建一个新的节点，将新差创建的节点放到链表头部
 * 如果超出容量后，就删除最下面的书
 * */

class LRUCache {
    private static class Node{
        int key,value;
        Node prev,next;

        Node(int k,int v){
            key = k;
            value = v;
        }
    }

    private final int capacity;
    // 哨兵节点
    private final Node dummy = new Node(0,0);
    private final Map<Integer,Node> keyToNode = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        // 建立循环链表，此时链表为空
        dummy.prev = dummy;
        dummy.next = dummy;
    }
    
    public int get(int key) {
        Node node = getNode(key);// getNode会把对应节点移到链表头部
        return node != null ? node.value : -1;
    }
    
    public void put(int key, int value) {
        Node node = getNode(key); // getNode会把对应节点移到链表头部
        if(node != null){ // 有这本书
            node.value = value; // 更新value
            return;
        }
        node = new Node(key,value); // 新书
        keyToNode.put(key,node);// 将新创建的节点放入哈希表中
        pushFront(node); // 放到最上面
        if(keyToNode.size() > capacity){ // 书太多了
            Node backNode = dummy.prev;
            keyToNode.remove(backNode.key);
            remove(backNode); // 去掉最后一本书
        }
    }
    // 获取key对应的节点，同时把该节点移到链表头部
    private Node getNode(int key){
        if(!keyToNode.containsKey(key)){
            return null;
        }
        Node node = keyToNode.get(key);
        remove(node); // 把这本书抽出
        pushFront(node);// 放到最上面
        return node;
    }

    // 删除一个节点（抽出一本书）
    private void remove(Node x){
        x.prev.next = x.next;
        x.next.prev = x.prev;
    }
    // 在链表头添加一个节点（把一本书放到最上面）相当于插入一个节点
    private void pushFront(Node x){
        x.prev = dummy;
        x.next = dummy.next;
        x.prev.next = x;
        x.next.prev = x;
    }
}